πŸ‘©β€πŸ’» 9466. ν…€ ν”„λ‘œμ νŠΈ

@Seongukbaek Posted January 22, 2022 Β· Updated January 22, 2022 Β· 5 min read

문제

이번 가을학기에 '문제 ν•΄κ²°' κ°•μ˜λ₯Ό μ‹ μ²­ν•œ 학생듀은 ν…€ ν”„λ‘œμ νŠΈλ₯Ό μˆ˜ν–‰ν•΄μ•Ό ν•œλ‹€. ν”„λ‘œμ νŠΈ νŒ€μ› μˆ˜μ—λŠ” μ œν•œμ΄ μ—†λ‹€. 심지어 λͺ¨λ“  학생듀이 λ™μΌν•œ νŒ€μ˜ νŒ€μ›μΈ κ²½μš°μ™€ 같이 ν•œ νŒ€λ§Œ μžˆμ„ μˆ˜λ„ μžˆλ‹€. ν”„λ‘œμ νŠΈ νŒ€μ„ κ΅¬μ„±ν•˜κΈ° μœ„ν•΄, λͺ¨λ“  학생듀은 ν”„λ‘œμ νŠΈλ₯Ό ν•¨κ»˜ν•˜κ³  싢은 학생을 선택해야 ν•œλ‹€. (단, 단 ν•œ λͺ…λ§Œ 선택할 수 μžˆλ‹€.) 혼자 ν•˜κ³  μ‹Άμ–΄ν•˜λŠ” 학생은 자기 μžμ‹ μ„ μ„ νƒν•˜λŠ” 것도 κ°€λŠ₯ν•˜λ‹€.

학생듀이(s1, s2, ..., sr)이라 ν•  λ•Œ, r=1이고 s1이 s1을 μ„ νƒν•˜λŠ” κ²½μš°λ‚˜, s1이 s2λ₯Ό μ„ νƒν•˜κ³ , s2κ°€ s3λ₯Ό μ„ νƒν•˜κ³ ,..., sr-1이 sr을 μ„ νƒν•˜κ³ , sr이 s1을 μ„ νƒν•˜λŠ” κ²½μš°μ—λ§Œ ν•œ νŒ€μ΄ 될 수 μžˆλ‹€.

μ–΄λŠ ν”„λ‘œμ νŠΈ νŒ€μ—λ„ μ†ν•˜μ§€ μ•ŠλŠ” ν•™μƒλ“€μ˜ 수λ₯Ό κ³„μ‚°ν•˜λŠ” ν”„λ‘œκ·Έλž¨μ„ μž‘μ„±ν•˜λΌ.

μž…λ ₯

  • 첫째 쀄에 ν…ŒμŠ€νŠΈ μΌ€μ΄μŠ€μ˜ 개수 Tκ°€ μ£Όμ–΄μ§„λ‹€. 각 ν…ŒμŠ€νŠΈ μΌ€μ΄μŠ€μ˜ 첫 μ€„μ—λŠ” ν•™μƒμ˜ μˆ˜κ°€ μ •μˆ˜ n (2 ≀ n ≀ 100,000)으둜 μ£Όμ–΄μ§„λ‹€. 각 ν…ŒμŠ€νŠΈ μΌ€μ΄μŠ€μ˜ λ‘˜μ§Έ μ€„μ—λŠ” μ„ νƒλœ ν•™μƒλ“€μ˜ λ²ˆν˜Έκ°€ μ£Όμ–΄μ§„λ‹€. (λͺ¨λ“  학생듀은 1λΆ€ν„° nκΉŒμ§€ λ²ˆν˜Έκ°€ λΆ€μ—¬λœλ‹€.)

좜λ ₯

  • 각 ν…ŒμŠ€νŠΈ μΌ€μ΄μŠ€λ§ˆλ‹€ ν•œ 쀄에 좜λ ₯ν•˜κ³ , 각 μ€„μ—λŠ” ν”„λ‘œμ νŠΈ νŒ€μ— μ†ν•˜μ§€ λͺ»ν•œ ν•™μƒλ“€μ˜ 수λ₯Ό λ‚˜νƒ€λ‚΄λ©΄ λœλ‹€.

πŸ“ Logic

class Graph { final int[] graph; int[] discovered; boolean[] fin; int answer = 0; int graph_size; public Graph(int size) { graph_size = size + 1; this.graph = new int[graph_size]; discovered = new int[graph_size]; fin = new boolean[graph_size]; } }
  • κ·Έλž˜ν”„μ˜ 정보λ₯Ό μ €μž₯ν•˜κΈ° μœ„ν•œ 클래슀
public void search(int node) { if (discovered[node] == 1) return; discovered[node] = 1; int next = graph[node]; if (discovered[next] == 0) search(graph[node]); else { if (!fin[next]) { answer++; for (int i=next; i!=node; i=graph[i]) { answer++; } } } fin[node] = true; }
  • λ‹€μŒ λ°©λ¬Έν•  정점이 λ°©λ¬Έν•˜μ§€ μ•Šμ€ κ²½μš°λŠ” search() 둜 DFS μˆ˜ν–‰
  • λ‹€μŒ 정점을 이미 λ°©λ¬Έν•œ 경우, fin[next] 둜 이미 사이클이 ν˜•μ„±λœ 정점인지 확인

    • κ·Έλ ‡μ§€ μ•Šμ€ 경우, λ‹€μ‹œ ν•΄λ‹Ή μ •μ μœΌλ‘œ λŒμ•„μ˜€κΈ° μ „κΉŒμ§€ ν•΄λ‹Ή 정점과 μ—°κ²°λœ μ •μ μ˜ 수λ₯Ό 카운트
    • 카운트의 합이 κ³§ νŒ€μ„ μ΄λ£¨λŠ” ν•™μƒλ“€μ΄λ―€λ‘œ, 전체 학생 - λˆ„μ  μΉ΄μš΄νŠΈκ°€ μ •λ‹΅

πŸ“„ CODE

μ½”λ“œ 보기/μ ‘κΈ°πŸ’«
import java.util.*; class Graph { final int[] graph; int[] discovered; boolean[] fin; int answer = 0; int graph_size; public Graph(int size) { graph_size = size + 1; this.graph = new int[graph_size]; discovered = new int[graph_size]; fin = new boolean[graph_size]; } public void AddElement(int x, int y) { graph[x] = y; } public int solution() { for (int i=1; i < graph_size; i++) this.search(i); return graph_size - 1 - this.answer; } public void search(int node) { if (discovered[node] == 1) return; discovered[node] = 1; int next = graph[node]; if (discovered[next] == 0) search(graph[node]); else { if (!fin[next]) { // λ‹€μŒ 갈 정점이 방문은 ν–ˆμœΌλ‚˜ 아직 λλ‚˜μ§€ μ•Šμ€, 즉 사이클이 μƒμ„±λ˜μ§€ μ•Šμ€ μƒνƒœ answer++; for (int i=next; i!=node; i=graph[i]) { answer++; } } } fin[node] = true; } } public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int T = sc.nextInt(); while (T > 0) { int size = sc.nextInt(); Graph g = new Graph(size); for (int i = 1; i <= size; i++) { int tmp = sc.nextInt(); g.AddElement(i, tmp); } System.out.println(g.solution()); T-=1; } sc.close(); } }

✏️ Review

  • 결ꡭ은 "사이클을 μ°Ύμ•„μ•Ό ν•œλ‹€" λΌλŠ” λ…Όλ¦¬λŠ” λ§žμ•˜μ§€λ§Œ, μ΅œμ ν™”λ₯Ό ν•΄λ‚΄μ§€ λͺ»ν•΄ μ‹œκ°„ 초과λ₯Ό ν”Όν•  수 μ—†μ—ˆλ‹€.
  • μ΄μ œλΆ€ν„°λŠ” ν•˜λ£¨μ— 1λ¬Έμ œλŠ” ν’€μ–΄μ•Όν•˜κΈ° λ•Œλ¬Έμ— λ„ˆλ¬΄ μ‹œκ°„μ„ μž‘μ•„ λ¨Ήμ§€ μ•ŠμœΌλ €κ³  풀이λ₯Ό μ°Έκ³ ν–ˆλ‹€.

πŸ“• 좜처

Baekjoon : https://www.acmicpc.net/problem/9466

μ°Έκ³ 

https://bcp0109.tistory.com/32

@Seongukbaek
배우고 μ •λ¦¬ν•˜κ³  κ³΅μœ ν•˜λŠ” λŒ€ν•™μƒ λ°±μ„±μš±μž…λ‹ˆλ‹€ πŸ˜€